package zcw.com.lib_leet_code;

import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/8/11.<br><br>
 *
 * 中等：修剪二叉搜索树
 */
public class Topic669 {

    public static void main(String[] args) {
        Topic669 instance = new Topic669();

        List<Integer> list = Arrays.asList(1,null,2);
        TreeNode root = Util.createTree(list);
        root = instance.trimBST(root, 1, 2);
        Util.preTravelTree(root);
        System.out.println();
        Util.inTravelTree(root);
        System.out.println();
        Util.postTravelTree(root);
        System.out.println();

        list = Arrays.asList(3,0,4,null,2,null,null,null,null,1);
        root = Util.createTree(list);
        root = instance.trimBST(root, 1, 3);
        Util.preTravelTree(root);
        System.out.println();
        Util.inTravelTree(root);
        System.out.println();
        Util.postTravelTree(root);
        System.out.println();
    }

    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) {
            return null;
        }

        if(root.val > high) {
            return trimBST(root.left, low, high);
        }

        if(root.val < low) {
            return trimBST(root.right, low, high);
        }

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
